package Ep02_LinkedList._0707;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/3/6 10:44
 * 说明：力扣 0707 设计链表 单链表
 */


public class SingleLinkedList{
    // size储存链表中元素的个数
    int size;
    // 虚拟头结点
    ListNode dummyHead;

    // 初始化链表，初始化时就加上虚拟头结点
    public SingleLinkedList(){
        size = 0;
        // 目前链表的尺寸为 0+dummyHead
        dummyHead = new ListNode(0);
    }

    // 寻找第index个节点的值
    public int get(int index){
        // 判断index合法
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode cur = dummyHead;
        // 因为有一个虚拟头结点，所以原来链表中第index个节点变成新链表中第index+1个节点
        // 每次遍历新节点，都将指针向后移动一位，因此假设index=2时，我们只需要找到index=1的节点即可
        for (int i = 0; i < index+1; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    //在链表最前面插入一个节点，等价于在第0个元素前添加
    public void addAtHead(int val){
        addAtIndex(0, val);
    }

    //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
    // 原链表长度为size，下标到size-1，如果以此调用addAtIndex(size-1, val)，则是在最后一个元素之前插入节点，不是在尾处插入
    // 因此，要在尾处插入节点，需要到size-1的后面，也就是size-1+1
    public void addAtTail(int val){
        addAtIndex(size, val);
    }

    // 在index节点之前添加一个新节点，只需要找到index的前驱节点
    public void addAtIndex(int index, int val){
        if (index > size){
            return;
        }
        if (index <= 0){
            index = 0;
        }
        ListNode pre = dummyHead;
        // 找到要插入节点的前驱结点
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pre.next;
        pre.next = toAdd;
        size++;
    }

    // 删除第index个节点，需要寻找index的前序节点
    public void deleteAtIndex(int index){
        if (index < 0 || index >= size){
            return;
        }
        if(index == 0){
            dummyHead = dummyHead.next;
            size--;
            return;
        }
        ListNode pre = dummyHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
    }
}
